# include <iostream>
#include <unordered_set>

// 思路和算法

// 判断两个链表是否相交，可以使用哈希集合存储链表节点。
// 1.首先遍历链表 headA，并将链表headA 中的每个节点加入哈希集合中。
// 2.然后遍历链表headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
// 如果当前节点不在哈希集合中，则继续遍历下一个节点；
// 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，
//因此在链表headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
// 如果链表headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回null。

//定义一个单链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(nullptr){}
};

class Solution
{
public:
ListNode *getIntersectionNode(ListNode *head_a,ListNode *head_b)
{
    std::unordered_set<ListNode *> visited;
    ListNode *temp=head_a;
    while (temp!=nullptr)
    {
        visited.insert(temp);
        temp=temp->next;
    }
    temp=head_b;
    while (temp!=nullptr)
    {
        if (visited.count(temp))
        {
            return temp;
        }
        temp=temp->next;
    }
    return nullptr;

}

};

int main(int argc,char **argv)
{
    ListNode a(4);
    ListNode b(1);
    ListNode c(8);
    ListNode d(4);
    ListNode e(5);
    ListNode aa(5);
    ListNode bb(6);

    a.next=&b;
    a.next->next=&c;
    a.next->next->next=&d;
    a.next->next->next->next=&e;

    aa.next=&bb;
    aa.next->next=&c;
    aa.next->next->next=&d;
    aa.next->next->next->next=&e;
    ListNode *node;

    node=&a;
    while (node->next!=nullptr)
    {
        std::cout<<node->val<<std::endl;
        node=node->next;
    }
    std::cout<<node->val<<std::endl;
    ListNode *node2=&aa;
    while (node2->next!=nullptr)
    {
        std::cout<<node2->val<<std::endl;
        node2=node2->next;
    }
    std::cout<<node->val<<std::endl;
    Solution solution;
    ListNode *re=solution.getIntersectionNode(&a,&aa);
    std::cout<<"result: \n"<<re->val<<std::endl;
    return 0;
}